package com.gitee.huanminabc.jcommon.container;

import lombok.extern.slf4j.Slf4j;

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;
import java.util.List;
import java.util.Objects;
import java.util.function.Supplier;

/**
 * 本地内存布隆过滤器工具类
 *
 * <p>使用 Java BitSet 实现的布隆过滤器，数据存储在本地内存中，适合单机场景。</p>
 *
 * <p><b>重要特性：</b></p>
 * <ul>
 *   <li><b>返回 false</b>：元素<b>肯定不存在</b>（100%准确，不会有误判）</li>
 *   <li><b>返回 true</b>：元素<b>可能存在</b>（可能有假阳性误判，需要用数据库等可靠数据源二次确认）</li>
 * </ul>
 *
 * <p><b>误判方向说明：</b></p>
 * <ul>
 *   <li>✅ <b>不会有假阴性</b>：不会把"存在的"误判为"不存在"（这是致命问题，但布隆过滤器保证不会发生）</li>
 *   <li>⚠️ <b>可能有假阳性</b>：可能把"不存在的"误判为"存在"（这个可以兜底，比如查询数据库确认）</li>
 * </ul>
 *
 * <p><b>使用方式：</b></p>
 * <pre>{@code
 * // 方式1：使用默认配置
 * BloomFilterLocalUtil.BloomFilter bloomFilter = BloomFilterLocalUtil.builder().build();
 *
 * // 方式2：自定义配置
 * BloomFilter filter = BloomFilterLocalUtil.builder()
 *     .bitSetSize(100_000_000L)
 *     .hashCount(3)
 *     .hashSeeds(new int[]{31, 131, 1313})
 *     .build();
 *
 * // 使用
 * filter.add("element123");
 * boolean exists = filter.mightContain("element123");
 *
 * // 清空布隆过滤器（清空内存中的位图）
 * filter.clear();
 * }</pre>
 *
 * <p><b>注意事项：</b></p>
 * <ul>
 *   <li>数据存储在本地内存中，应用重启后数据会丢失</li>
 *   <li>支持大容量（通过多个 BitSet 分段存储），每个分段最大支持 Integer.MAX_VALUE 位</li>
 *   <li>线程安全：虽然 Java 的 BitSet 不是线程安全的，但本实现通过 synchronized 同步块保证所有关键操作（add、mightContain、clear）的线程安全性</li>
 *   <li>内存占用：默认配置（1亿位）约占用 12.5 MB 内存。可通过 {@link #calculateMemoryUsage(long)} 方法计算指定大小的内存占用</li>
 * </ul>
 *
 * @author sby-plugin-common
 * @since 1.0.0
 */
@Slf4j
public class BloomFilterLocalUtil {

    /**
     * 默认BitSet大小：1亿位
     */
    private static final long DEFAULT_BIT_SET_SIZE = 100_000_000L;

    /**
     * 默认Hash函数数量（使用多个hash函数降低误判率）
     */
    private static final int DEFAULT_HASH_COUNT = 3;

    /**
     * 默认Hash函数种子（不同的种子生成不同的hash值）
     */
    private static final int[] DEFAULT_HASH_SEEDS = {31, 131, 1313};

    /**
     * 每个 BitSet 分段的最大容量（Integer.MAX_VALUE）
     */
    private static final long SEGMENT_SIZE = Integer.MAX_VALUE;

    /**
     * 创建布隆过滤器构建器
     *
     * @return 构建器实例
     */
    public static BloomFilter builder() {
        return new BloomFilterBuilder().build();
    }

    /**
     * 布隆过滤器构建器
     */
    public static class BloomFilterBuilder {
        private long bitSetSize = DEFAULT_BIT_SET_SIZE;
        private int hashCount = DEFAULT_HASH_COUNT;
        private int[] hashSeeds = DEFAULT_HASH_SEEDS;

        /**
         * 设置BitSet大小（位数）
         *
         * @param bitSetSize BitSet大小
         * @return 构建器自身
         */
        public BloomFilterBuilder bitSetSize(long bitSetSize) {
            this.bitSetSize = bitSetSize;
            return this;
        }

        /**
         * 设置Hash函数数量
         *
         * @param hashCount Hash函数数量
         * @return 构建器自身
         */
        public BloomFilterBuilder hashCount(int hashCount) {
            this.hashCount = hashCount;
            return this;
        }

        /**
         * 设置Hash函数种子数组
         *
         * @param hashSeeds Hash函数种子数组
         * @return 构建器自身
         */
        public BloomFilterBuilder hashSeeds(int[] hashSeeds) {
            this.hashSeeds = hashSeeds;
            return this;
        }

        /**
         * 构建布隆过滤器实例
         *
         * @return 布隆过滤器实例
         */
        public BloomFilter build() {
            return new BloomFilter(bitSetSize, hashCount, hashSeeds);
        }
    }

    /**
     * 布隆过滤器实例
     */
    public static class BloomFilter {
        private final long bitSetSize;
        private final int hashCount;
        private final int[] hashSeeds;
        private final BitSet[] bitSets;
        private final int segmentCount;

        private BloomFilter(long bitSetSize, int hashCount, int[] hashSeeds) {
            this.bitSetSize = bitSetSize;
            this.hashCount = hashCount;
            this.hashSeeds = hashSeeds;
            
            // 计算需要多少个分段
            this.segmentCount = (int) Math.ceil((double) bitSetSize / SEGMENT_SIZE);
            
            // 初始化分段 BitSet 数组
            this.bitSets = new BitSet[segmentCount];
            for (int i = 0; i < segmentCount; i++) {
                // 最后一个分段可能不需要完整的 SEGMENT_SIZE
                long segmentBitSize = (i == segmentCount - 1) 
                    ? (bitSetSize - i * SEGMENT_SIZE) 
                    : SEGMENT_SIZE;
                bitSets[i] = new BitSet((int) segmentBitSize);
            }
            
            log.debug("BloomFilter初始化完成，bitSetSize: {}, segmentCount: {}", bitSetSize, segmentCount);
        }

        /**
         * 根据位索引获取对应的分段索引和分段内索引
         *
         * @param bitIndex 全局位索引
         * @return 数组，[0]为分段索引，[1]为分段内索引
         */
        private int[] getSegmentIndex(long bitIndex) {
            int segmentIndex = (int) (bitIndex / SEGMENT_SIZE);
            int segmentBitIndex = (int) (bitIndex % SEGMENT_SIZE);
            return new int[]{segmentIndex, segmentBitIndex};
        }

        /**
         * 判断元素是否可能存在
         *
         * <p><b>重要特性：</b></p>
         * <ul>
         *   <li><b>返回 false</b>：元素<b>肯定不存在</b>（100%准确，不会有误判）</li>
         *   <li><b>返回 true</b>：元素<b>可能存在</b>（可能有假阳性误判，需要用数据库等可靠数据源二次确认）</li>
         * </ul>
         *
         * @param element 要判断的元素
         * @return true表示可能存在（需要二次确认），false表示肯定不存在（100%准确）
         */
        public boolean mightContain(String element) {
            if (element == null || element.isEmpty()) {
                return false;
            }

            try {
                synchronized (this) {
                    // 检查所有hash位置的位是否都为1
                    for (int i = 0; i < hashCount; i++) {
                        long bitIndex = getBitIndex(element, hashSeeds[i]);
                        int[] segmentInfo = getSegmentIndex(bitIndex);
                        int segmentIdx = segmentInfo[0];
                        int segmentBitIdx = segmentInfo[1];
                        
                        // 检查分段索引是否有效
                        if (segmentIdx >= segmentCount) {
                            log.warn("BloomFilter::mightContain 分段索引超出范围，bitIndex: {}, segmentIdx: {}, segmentCount: {}", 
                                bitIndex, segmentIdx, segmentCount);
                            return false;
                        }
                        
                        BitSet segment = bitSets[segmentIdx];
                        if (segment == null || !segment.get(segmentBitIdx)) {
                            // 如果任何一个位为0，则肯定不存在（100%准确，不会有假阴性）
                            return false;
                        }
                    }
                    // 所有位都为1，可能存在（但可能有假阳性，需要二次确认）
                    return true;
                }
            } catch (Exception e) {
                log.error("BloomFilter::mightContain 判断元素是否已存在失败，element: {}", element, e);
                // 异常时返回false，走数据库查询兜底
                return false;
            }
        }

        /**
         * 利用函数如果存在就执行函数不存在就添加数据
         *
         * @param element 要判断的元素
         * @param addThrowable 添加异常比如数据库的唯一索引触发后需要将数据添加到过滤器中
         * @param get 查询函数，用于二次确认元素是否在数据源中存在，返回true表示数据源中存在，返回false表示数据源中不存在
         * @param consumer 添加函数，用于执行添加操作，建议加一个轻量锁来控制写入并发
         */
        public void mightContainAccurate(String element, Class<? extends RuntimeException> addThrowable, Supplier<Boolean> get, Runnable consumer) {
            Objects.requireNonNull(element);
            try {
                if (mightContain(element)) {
                    Boolean apply = get.get();
                    //数据源内一定存在
                    if (apply) {
                        return;
                    }
                    //二次确认后不存在那么就执行添加
                    consumer.run();
                } else {
                    consumer.run();
                }
                add(element);
            } catch (Throwable e) {
                //判断异常是否符合添加异常
                if (addThrowable.isAssignableFrom(e.getClass())) {
                    add(element);
                }else {
                    throw e;
                }
            }
        }

        /**
         * 将元素添加到布隆过滤器
         *
         * @param element 要添加的元素
         */
        public void add(String element) {
            if (element == null || element.isEmpty()) {
                return;
            }

            try {
                synchronized (this) {
                    // 将所有hash位置的位设置为1
                    for (int i = 0; i < hashCount; i++) {
                        long bitIndex = getBitIndex(element, hashSeeds[i]);
                        int[] segmentInfo = getSegmentIndex(bitIndex);
                        int segmentIdx = segmentInfo[0];
                        int segmentBitIdx = segmentInfo[1];
                        
                        // 检查分段索引是否有效
                        if (segmentIdx >= segmentCount) {
                            log.warn("BloomFilter::add 分段索引超出范围，bitIndex: {}, segmentIdx: {}, segmentCount: {}", 
                                bitIndex, segmentIdx, segmentCount);
                            continue;
                        }
                        
                        BitSet segment = bitSets[segmentIdx];
                        if (segment != null) {
                            segment.set(segmentBitIdx, true);
                        }
                    }
                    log.debug("BloomFilter::add 元素已加入布隆过滤器，element: {}", element);
                }
            } catch (Exception e) {
                log.error("BloomFilter::add 添加元素到布隆过滤器失败，element: {}", element, e);
            }
        }

        /**
         * 批量添加元素到布隆过滤器
         *
         * @param elements 要添加的元素列表
         */
        public void addBatch(List<String> elements) {
            if (elements == null || elements.isEmpty()) {
                return;
            }
            for (String element : elements) {
                add(element);
            }
        }

        /**
         * 计算元素在BitSet中的位置
         * 使用MD5 + hash种子计算，确保一致性
         *
         * @param element 元素
         * @param seed    hash种子
         * @return BitSet中的位置索引（0到bitSetSize-1）
         */
        private long getBitIndex(String element, int seed) {
            try {
                // 使用MD5生成hash值
                MessageDigest md5 = MessageDigest.getInstance("MD5");
                byte[] hashBytes = md5.digest((element + seed).getBytes(StandardCharsets.UTF_8));

                // 将hash值转换为long，并取模
                long hashValue = 0;
                for (int i = 0; i < Math.min(8, hashBytes.length); i++) {
                    hashValue = (hashValue << 8) | (hashBytes[i] & 0xFF);
                }

                // 确保结果为正数并取模
                long index = Math.abs(hashValue) % bitSetSize;
                return index;
            } catch (NoSuchAlgorithmException e) {
                // MD5算法不存在（理论上不会发生），使用简单hash
                long hashValue = (element + seed).hashCode();
                return Math.abs(hashValue) % bitSetSize;
            }
        }

        /**
         * 计算布隆过滤器的误判率（假阳性率）
         * 公式：p ≈ (1 - e^(-kn/m))^k
         *
         * @param expectedElements 预期插入的元素数量
         * @return 误判率（0.0到1.0之间，例如0.01表示1%的误判率）
         */
        public double calculateFalsePositiveRate(long expectedElements) {
            if (bitSetSize <= 0 || hashCount <= 0 || expectedElements <= 0) {
                return 1.0;
            }
            // p ≈ (1 - e^(-kn/m))^k
            double exponent = -(hashCount * expectedElements) / (double) bitSetSize;
            double base = 1 - Math.exp(exponent);
            return Math.pow(base, hashCount);
        }

        /**
         * 获取当前配置的BitSet大小
         *
         * @return BitSet大小（位数）
         */
        public long getBitSetSize() {
            return bitSetSize;
        }

        /**
         * 获取当前配置的Hash函数数量
         *
         * @return Hash函数数量
         */
        public int getHashCount() {
            return hashCount;
        }

        /**
         * 获取分段数量
         *
         * @return 分段数量
         */
        public int getSegmentCount() {
            return segmentCount;
        }

        /**
         * 获取Hash函数种子数组
         *
         * @return Hash函数种子数组
         */
        public int[] getHashSeeds() {
            return hashSeeds.clone();
        }

        /**
         * 获取当前布隆过滤器占用的内存（字节数）
         *
         * @return 内存占用（字节数）
         */
        public long getMemoryUsage() {
            return calculateMemoryUsage(bitSetSize);
        }

        /**
         * 获取当前布隆过滤器占用的内存（格式化字符串）
         *
         * @return 格式化后的内存占用，如 "12.5 MB"
         */
        public String getMemoryUsageFormatted() {
            return formatMemoryUsage(getMemoryUsage());
        }

        /**
         * 清空布隆过滤器（清空内存中的位图）
         *
         * <p>注意：此操作会清空内存中的整个布隆过滤器，删除后需要重新添加元素。</p>
         *
         * @return true表示清空成功
         */
        public boolean clear() {
            try {
                synchronized (this) {
                    for (int i = 0; i < segmentCount; i++) {
                        if (bitSets[i] != null) {
                            bitSets[i].clear();
                        }
                    }
                    log.debug("BloomFilter::clear 布隆过滤器已清空");
                    return true;
                }
            } catch (Exception e) {
                log.error("BloomFilter::clear 清空布隆过滤器失败", e);
                return false;
            }
        }
    }

    /**
     * 计算布隆过滤器的误判率（假阳性率）
     * 公式：p ≈ (1 - e^(-kn/m))^k
     *
     * @param bitSetSize       BitSet大小（位数）
     * @param hashCount        Hash函数数量
     * @param expectedElements 预期插入的元素数量
     * @return 误判率（0.0到1.0之间，例如0.01表示1%的误判率）
     */
    public static double calculateFalsePositiveRate(long bitSetSize, int hashCount, long expectedElements) {
        if (bitSetSize <= 0 || hashCount <= 0 || expectedElements <= 0) {
            return 1.0;
        }
        // p ≈ (1 - e^(-kn/m))^k
        double exponent = -(hashCount * expectedElements) / (double) bitSetSize;
        double base = 1 - Math.exp(exponent);
        return Math.pow(base, hashCount);
    }

    /**
     * 根据预期的元素数量和目标误判率，计算最优的BitSet大小
     * 公式：m = -n * ln(p) / (ln(2)^2)
     *
     * @param expectedElements        预期插入的元素数量
     * @param targetFalsePositiveRate 目标误判率（例如0.01表示1%）
     * @return 推荐的BitSet大小（位数）
     */
    public static long calculateOptimalBitSetSize(long expectedElements, double targetFalsePositiveRate) {
        if (expectedElements <= 0 || targetFalsePositiveRate <= 0 || targetFalsePositiveRate >= 1) {
            return DEFAULT_BIT_SET_SIZE;
        }
        // m = -n * ln(p) / (ln(2)^2)
        double ln2 = Math.log(2);
        double lnp = Math.log(targetFalsePositiveRate);
        return (long) Math.ceil(-expectedElements * lnp / (ln2 * ln2));
    }

    /**
     * 根据预期的元素数量和BitSet大小，计算最优的Hash函数数量
     * 公式：k = (m/n) * ln(2)
     *
     * @param expectedElements 预期插入的元素数量
     * @param bitSetSize       BitSet大小（位数）
     * @return 推荐的Hash函数数量
     */
    public static int calculateOptimalHashCount(long expectedElements, long bitSetSize) {
        if (expectedElements <= 0 || bitSetSize <= 0) {
            return DEFAULT_HASH_COUNT;
        }
        // k = (m/n) * ln(2)
        double optimalK = (bitSetSize / (double) expectedElements) * Math.log(2);
        return Math.max(1, (int) Math.round(optimalK));
    }

    /**
     * 计算指定BitSet大小占用的内存（字节数）
     * 
     * <p>BitSet内部使用long数组存储位，每个long占用8字节，可存储64位。</p>
     * <p>内存占用 = ceil(bitSetSize / 64) * 8 + 对象开销</p>
     * 
     * <p><b>示例：</b></p>
     * <ul>
     *   <li>1亿位（100,000,000位）≈ 12.5 MB</li>
     *   <li>10亿位（1,000,000,000位）≈ 125 MB</li>
     * </ul>
     *
     * @param bitSetSize BitSet大小（位数）
     * @return 内存占用（字节数）
     */
    public static long calculateMemoryUsage(long bitSetSize) {
        if (bitSetSize <= 0) {
            return 0;
        }
        // BitSet内部使用long数组，每个long是64位，占用8字节
        // 需要的long数量 = ceil(bitSetSize / 64)
        long longCount = (bitSetSize + 63) / 64;
        // 每个long占用8字节
        long arraySize = longCount * 8;
        // 加上数组对象头（约24字节）和BitSet对象本身的开销（约40字节）
        // 分段存储时，每个分段都有这些开销
        int segmentCount = (int) Math.ceil((double) bitSetSize / SEGMENT_SIZE);
        long segmentOverhead = segmentCount * (24 + 40); // 数组头 + BitSet对象头
        return arraySize + segmentOverhead;
    }

    /**
     * 格式化内存占用为人类可读的字符串
     *
     * @param bytes 字节数
     * @return 格式化后的字符串，如 "12.5 MB"
     */
    public static String formatMemoryUsage(long bytes) {
        if (bytes < 1024) {
            return bytes + " B";
        } else if (bytes < 1024 * 1024) {
            return String.format("%.2f KB", bytes / 1024.0);
        } else if (bytes < 1024 * 1024 * 1024) {
            return String.format("%.2f MB", bytes / (1024.0 * 1024.0));
        } else {
            return String.format("%.2f GB", bytes / (1024.0 * 1024.0 * 1024.0));
        }
    }
}

